﻿using System.Threading;

namespace Jiubang.Collections {
    internal sealed class ConcurrentLinkedQueue<T> {
        private Node<T> _head;
        private Node<T> _tail;

        public ConcurrentLinkedQueue() {
            _head = new Node<T>(default(T), null);
            _tail = _head;
        }

        public bool IsEmpty {
            get { return (_head.Next == null); }
        }

        public void Enqueue(T item) {
            var newNode = new Node<T>(item, null);
            while (true) {
                var tail = _tail;
                // ReSharper disable PossibleNullReferenceException
                var next = tail.Next;
                // ReSharper restore PossibleNullReferenceException

                //判断_tail是否被其他process改变
                if (tail == _tail) {
                    //A 有其他process执行C成功，_tail应该指向新的节点
                    if (next == null) {
                        //C 如果其他process改变了tail.next节点，需要重新取新的tail节点
                        if (Interlocked.CompareExchange(ref tail.Next, newNode, next) == next) {
                            //D 尝试修改tail
                            Interlocked.CompareExchange(ref _tail, newNode, tail);
                            return;
                        }
                    } else {
                        //B 帮助其他线程完成D操作
                        Interlocked.CompareExchange(ref _tail, next, tail);
                    }
                }
            }
        }

        public bool TryDequeue(out T result) {
            do {
                var head = _head;
                var curTail = _tail;
                // ReSharper disable PossibleNullReferenceException
                var next = head.Next;
                // ReSharper restore PossibleNullReferenceException

                if (head == _head) {
                    if (next == null) //Queue为空
                    {
                        result = default(T);
                        return false;
                    }
                    if (head == curTail) //Queue处于Enqueue第一个node的过程中
                    {
                        //尝试帮助其他Process完成操作
                        Interlocked.CompareExchange(ref _tail, next, curTail);
                    } else {
                        //取next.Item必须放到CAS之前
                        result = next.Item;
                        //如果_head没有发生改变，则将_head指向next并退出
                        if (Interlocked.CompareExchange(ref _head, next, head) == head)
                            break;
                    }
                }
            } while (true);
            return true;
        }

        #region Nested type: Node

        private sealed class Node<TItem> {
            internal readonly TItem Item;
            internal Node<TItem> Next;

            public Node(TItem item, Node<TItem> next) {
                Item = item;
                Next = next;
            }
        }

        #endregion
    }
}